package com.shm.mostRight;

import java.util.List;
import java.util.Stack;

/**
 * 反转链表
 * @author SHM
 */
public class Main3 {
    public static void main(String[] args) {
        ListNode root = new ListNode(1);
        root.next = new ListNode(2);
        root.next.next= new ListNode(3);
        ListNode reverse = reverse_4(root);
        while (reverse!=null){
            System.out.println(reverse.val);
            reverse = reverse.next;
        }

    }

    public static ListNode reverse(ListNode root){
        ListNode p = new ListNode(0);
        ListNode q = root;
        ListNode q1;
        while (q!=null){
            q1 = new ListNode(q.val);
            q1.next = p.next;
            p.next = q1;
            q = q.next;
        }
        return p.next;
    }

    public static ListNode reverse_2(ListNode root){
        ListNode p = new ListNode(0);
        ListNode q = root;
        while (q!=null){
            ListNode q1 = q.next;
            q.next = p.next;
            p.next = q;
            q = q1;
        }
        return p.next;
    }

    public static ListNode reverse_3(ListNode root){
        ListNode p = null;
        ListNode q;
        while (root!=null){
            q = root.next;
            root.next = p;
            p = root;
            root = q;
        }
        return p;
    }

    public static ListNode reverse_4(ListNode root){
        if (root==null||root.next==null){
            return root;
        }

        ListNode p = root;
        Stack<ListNode> stack = new Stack<>();
        while (p.next!=null){
            stack.push(p);
            p = p.next;
        }

        ListNode q = p;
        while (!stack.isEmpty()){
            p.next = stack.peek();
            p = p.next;
            stack.pop();
        }
        p.next = null;
        return q;
    }

}
class ListNode{
    int val;
    ListNode next;
    ListNode(int val){
        this.val = val;
    }
}